Verbal arithmetic puzzle¶
Time: O(10!xNxL); Space: O(NxL); hard
Given an equation, represented by words on left side and the result on right side.
You need to check if the equation is solvable under the following rules: * Each character is decoded as one digit (0 - 9). * Every pair of different characters they must map to different digits. * Each words[i] and result are decoded as one number without leading zeros. * Sum of numbers on left side (words) will equal to the number on right side (result).
Return True if the equation is solvable otherwise return False.
Example 1:
Input: words = [“SEND”,“MORE”], result = “MONEY”
Output: True
Explanation:
Map ‘S’-> 9, ‘E’->5, ‘N’->6, ‘D’->7, ‘M’->1, ‘O’->0, ‘R’->8, ‘Y’->‘2’
Such that: “SEND” + “MORE” = “MONEY” , 9567 + 1085 = 10652
Example 2:
Input: words = [“SIX”,“SEVEN”,“SEVEN”], result = “TWENTY”
Output: True
Explanation:
Map ‘S’-> 6, ‘I’->5, ‘X’->0, ‘E’->8, ‘V’->7, ‘N’->2, ‘T’->1, ‘W’->‘3’, ‘Y’->4
Such that: “SIX” + “SEVEN” + “SEVEN” = “TWENTY” , 650 + 68782 + 68782 = 138214
Example 3:
Input: words = [“THIS”,“IS”,“TOO”], result = “FUNNY”
Output: True
Example 4:
Input: words = [“LEET”,“CODE”], result = “POINT”
Output: False
Constraints:
2 <= words.length <= 5
1 <= words[i].length, result.length <= 7
words[i], result contains only upper case English letters.
Number of different characters used on the expression is at most 10.
Hints:
Use Backtracking and pruning to solve this problem.
If you set the values of some digits (from right to left), the other digits will be constrained.
[1]:
import collections
class Solution1(object):
"""
Time: O(10!*N*L)
Space: O(N*L)
"""
def isSolvable(self, words, result):
"""
:type words: List[str]
:type result: str
:rtype: bool
"""
def backtracking(words, result, i, j, carry, lookup, used):
if j == len(result):
return carry == 0
if i != len(words):
if j >= len(words[i]) or words[i][j] in lookup:
return backtracking(words, result, i+1, j, carry, lookup, used)
for val in range(10):
if val in used or (val == 0 and j == len(words[i])-1):
continue
lookup[words[i][j]] = val
used.add(val)
if backtracking(words, result, i+1, j, carry, lookup, used):
return True
used.remove(val)
del lookup[words[i][j]]
return False
carry, val = divmod(carry + sum(lookup[w[j]] for w in words if j < len(w)), 10)
if result[j] in lookup:
return val == lookup[result[j]] and \
backtracking(words, result, 0, j+1, carry, lookup, used)
if val in used or (val == 0 and j == len(result)-1):
return False
lookup[result[j]] = val
used.add(val)
if backtracking(words, result, 0, j+1, carry, lookup, used):
return True
used.remove(val)
del lookup[result[j]]
return False
return backtracking([w[::-1] for w in words], result[::-1], 0, 0, 0, {}, set())
[2]:
s = Solution1()
words = ["SEND","MORE"]
result = "MONEY"
assert s.isSolvable(words, result) == True
words = ["SIX","SEVEN","SEVEN"]
result = "TWENTY"
assert s.isSolvable(words, result) == True
words = ["THIS","IS","TOO"]
result = "FUNNY"
assert s.isSolvable(words, result) == True
words = ["LEET","CODE"]
result = "POINT"
assert s.isSolvable(words, result) == False